<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/myblog/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/myblog/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/myblog/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/myblog/images/logo.svg" color="#222">

<link rel="stylesheet" href="/myblog/css/main.css">


<link rel="stylesheet" href="/myblog/lib/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/myblog/lib/pace/pace-theme-minimal.min.css">
  <script src="/myblog/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"gao-qianwei.gitee.io","root":"/myblog/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="&amp;ensp;&amp;ensp;&amp;ensp;&amp;ensp;对于二叉树的遍历模板，运用到实际题目中才能熟练掌握其精髓，下面是以前做过的相关算法题，现在整理了出来。">
<meta property="og:type" content="article">
<meta property="og:title" content="遍历二叉树的几个算法题">
<meta property="og:url" content="https://gao-qianwei.gitee.io/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/index.html">
<meta property="og:site_name" content="学无止境">
<meta property="og:description" content="&amp;ensp;&amp;ensp;&amp;ensp;&amp;ensp;对于二叉树的遍历模板，运用到实际题目中才能熟练掌握其精髓，下面是以前做过的相关算法题，现在整理了出来。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gao-qianwei.gitee.io/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/1.png">
<meta property="og:image" content="https://gao-qianwei.gitee.io/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/2.png">
<meta property="og:image" content="https://gao-qianwei.gitee.io/myblog/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/3.png">
<meta property="og:image" content="https://gao-qianwei.gitee.io/myblog/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/4.jpg">
<meta property="article:published_time" content="2021-05-07T08:03:50.000Z">
<meta property="article:modified_time" content="2021-05-07T11:24:17.962Z">
<meta property="article:author" content="高乾威">
<meta property="article:tag" content="leetcode">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="二叉树">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gao-qianwei.gitee.io/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/1.png">

<link rel="canonical" href="https://gao-qianwei.gitee.io/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>遍历二叉树的几个算法题 | 学无止境</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/myblog/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">学无止境</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/myblog/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/myblog/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/myblog/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/myblog/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/myblog/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/myblog/links/" rel="section"><i class="fa fa-link fa-fw"></i>友链</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://gao-qianwei.gitee.io/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/myblog/images/avatar.png">
      <meta itemprop="name" content="高乾威">
      <meta itemprop="description" content="报我楼成秋望月，把君诗读夜回灯">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="学无止境">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          遍历二叉树的几个算法题
        </h1>

        <div class="post-meta">

          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-05-07 16:03:50 / 修改时间：19:24:17" itemprop="dateCreated datePublished" datetime="2021-05-07T16:03:50+08:00">2021-05-07</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/myblog/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
                </span>
                  ，
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/myblog/categories/%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E6%A0%91/" itemprop="url" rel="index"><span itemprop="name">二叉树</span></a>
                </span>
            </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>
            <span class="post-meta-divider">|</span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <p>&ensp;&ensp;&ensp;&ensp;对于二叉树的遍历模板，运用到实际题目中才能熟练掌握其精髓，下面是以前做过的相关算法题，现在整理了出来。</p>
<span id="more"></span>

<h4 id="98-验证二叉搜索树"><a href="#98-验证二叉搜索树" class="headerlink" title="98. 验证二叉搜索树"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/validate-binary-search-tree/">98. 验证二叉搜索树</a></h4><p>&ensp;&ensp;&ensp;&ensp;给定一个二叉树，判断其是否是一个有效的二叉搜索树。</p>
<p>&ensp;&ensp;&ensp;&ensp;假设一个二叉搜索树具有如下特征：</p>
<ul>
<li>  节点的左子树只包含<strong>小于</strong>当前节点的数。</li>
<li>  节点的右子树只包含<strong>大于</strong>当前节点的数。</li>
<li>  所有左子树和右子树自身必须也是二叉搜索树。</li>
</ul>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">输入:</span><br><span class="line">    2</span><br><span class="line">   &#x2F; \</span><br><span class="line">  1   3</span><br><span class="line">输出: true</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">输入:</span><br><span class="line">    5</span><br><span class="line">   &#x2F; \</span><br><span class="line">  1   4</span><br><span class="line">     &#x2F; \</span><br><span class="line">    3   6</span><br><span class="line">输出: false</span><br><span class="line">解释: 输入为: [5,1,4,null,null,3,6]。</span><br><span class="line">     根节点的值为 5 ，但是其右子节点值为 4 。</span><br></pre></td></tr></table></figure>

<p><strong>思路与代码</strong>：</p>
<p>&ensp;&ensp;&ensp;&ensp;遍历每个节点，记录好它的边界值，比如对于<code>root</code>的左子节点，它的最大值小于<code>root-&gt;val</code>，对于<code>root</code>的右子节点，它的最小值大于<code>root-&gt;val</code>。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for a binary tree node.</span></span><br><span class="line"><span class="comment"> * struct TreeNode &#123;</span></span><br><span class="line"><span class="comment"> *     int val;</span></span><br><span class="line"><span class="comment"> *     TreeNode *left;</span></span><br><span class="line"><span class="comment"> *     TreeNode *right;</span></span><br><span class="line"><span class="comment"> *     TreeNode() : val(0), left(nullptr), right(nullptr) &#123;&#125;</span></span><br><span class="line"><span class="comment"> *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) &#123;&#125;</span></span><br><span class="line"><span class="comment"> *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) &#123;&#125;</span></span><br><span class="line"><span class="comment"> * &#125;;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">isValidBST</span><span class="params">(TreeNode* root)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">isValidBST</span>(root, <span class="literal">nullptr</span>, <span class="literal">nullptr</span>);</span><br><span class="line">    &#125;</span><br><span class="line">	<span class="comment">//min, max 负责记录边界值</span></span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">isValidBST</span><span class="params">(TreeNode* root, TreeNode* min, TreeNode* max)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">if</span>(min != <span class="literal">nullptr</span> &amp;&amp; root-&gt;val &lt;= min-&gt;val)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">if</span>(max != <span class="literal">nullptr</span> &amp;&amp; root-&gt;val &gt;= max-&gt;val)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">isValidBST</span>(root-&gt;left, min, root)</span><br><span class="line">                &amp;&amp; <span class="built_in">isValidBST</span>(root-&gt;right, root, max);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h4 id="102-二叉树的层序遍历"><a href="#102-二叉树的层序遍历" class="headerlink" title="102. 二叉树的层序遍历"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/binary-tree-level-order-traversal/">102. 二叉树的层序遍历</a></h4><p>&ensp;&ensp;&ensp;&ensp;给你一个二叉树，请你返回其按 <strong>层序遍历</strong> 得到的节点值。 （即逐层地，从左到右访问所有节点）。</p>
<p><strong>示例：</strong><br>&ensp;&ensp;&ensp;&ensp;二叉树：<code>[3,9,20,null,null,15,7]</code>,</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">  3</span><br><span class="line"> &#x2F; \</span><br><span class="line">9  20</span><br><span class="line">  &#x2F;  \</span><br><span class="line"> 15   7</span><br></pre></td></tr></table></figure>

<p>&ensp;&ensp;&ensp;&ensp;返回其层序遍历结果：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[</span><br><span class="line">  [3],</span><br><span class="line">  [9,20],</span><br><span class="line">  [15,7]</span><br><span class="line">]</span><br></pre></td></tr></table></figure>

<p>&ensp;&ensp;&ensp;&ensp;思路与代码：有递归和迭代两种。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt; <span class="built_in">levelOrder</span>(TreeNode* root) </span><br><span class="line">    &#123;</span><br><span class="line">        vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt; ans;</span><br><span class="line">        <span class="built_in">pre</span>(root, <span class="number">0</span>, ans);</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">pre</span><span class="params">(TreeNode* root, <span class="keyword">int</span> depth, vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt; &amp;ans)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        <span class="comment">//先序遍历，遍历过程中记录层数</span></span><br><span class="line">        <span class="keyword">if</span> (depth &gt;= ans.<span class="built_in">size</span>())</span><br><span class="line">            ans.<span class="built_in">push_back</span>(vector&lt;<span class="keyword">int</span>&gt; &#123;&#125;);</span><br><span class="line">        ans[depth].<span class="built_in">push_back</span>(root-&gt;val);</span><br><span class="line">        <span class="built_in">pre</span>(root-&gt;left, depth + <span class="number">1</span>, ans);</span><br><span class="line">        <span class="built_in">pre</span>(root-&gt;right, depth + <span class="number">1</span>, ans);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>&ensp;&ensp;&ensp;&ensp;另一解法</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt; <span class="built_in">levelOrder</span>(TreeNode* root) </span><br><span class="line">    &#123;</span><br><span class="line">        queue&lt;TreeNode*&gt; que;</span><br><span class="line">        que.<span class="built_in">push</span>(root);</span><br><span class="line">        vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt; res;</span><br><span class="line">        <span class="keyword">while</span> (que.<span class="built_in">size</span>() != <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">int</span> size = que.<span class="built_in">size</span>();</span><br><span class="line">            vector&lt;<span class="keyword">int</span>&gt; level;</span><br><span class="line">            <span class="keyword">while</span> (size --) &#123;</span><br><span class="line">                TreeNode* cur = que.<span class="built_in">front</span>();</span><br><span class="line">                que.<span class="built_in">pop</span>();</span><br><span class="line">                <span class="keyword">if</span> (!cur) &#123;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                level.<span class="built_in">push_back</span>(cur-&gt;val);</span><br><span class="line">                que.<span class="built_in">push</span>(cur-&gt;left);</span><br><span class="line">                que.<span class="built_in">push</span>(cur-&gt;right);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (level.<span class="built_in">size</span>() != <span class="number">0</span>) &#123;</span><br><span class="line">                res.<span class="built_in">push_back</span>(level);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h4 id="230-二叉搜索树中第K小的元素"><a href="#230-二叉搜索树中第K小的元素" class="headerlink" title="230. 二叉搜索树中第K小的元素"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/">230. 二叉搜索树中第K小的元素</a></h4><p>&ensp;&ensp;&ensp;&ensp;给定一个二叉搜索树的根节点 <code>root</code> ，和一个整数 <code>k</code> ，请你设计一个算法查找其中第 <code>k</code> 个最小元素（从 1 开始计数）。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">    3</span><br><span class="line">   &#x2F; \</span><br><span class="line">  1   4</span><br><span class="line">   \   </span><br><span class="line">    2   </span><br><span class="line">输入：root &#x3D; [3,1,4,null,2], k &#x3D; 1</span><br><span class="line">输出：1</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">        5</span><br><span class="line">       &#x2F; \</span><br><span class="line">      3   6</span><br><span class="line">     &#x2F; \  </span><br><span class="line">    2   4 </span><br><span class="line">   &#x2F;</span><br><span class="line">  1 </span><br><span class="line">输入：root &#x3D; [5,3,6,2,4,null,null,1], k &#x3D; 3</span><br><span class="line">输出：3</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  树中的节点数为 <code>n</code> 。</li>
<li>  <code>1 &lt;= k &lt;= n &lt;= 104</code></li>
<li>  <code>0 &lt;= Node.val &lt;= 104</code></li>
</ul>
<p><strong>进阶：</strong>如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 <code>k</code> 小的值，你将如何优化算法？</p>
<p><strong>思路与代码</strong>：</p>
<p>&ensp;&ensp;&ensp;&ensp;BST的中序遍历为升序数组，所以一边中序遍历一边记录已查找的个数即可。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> rank = <span class="number">0</span>;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">traves</span><span class="params">(TreeNode* root, <span class="keyword">int</span> k)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        </span><br><span class="line">        <span class="built_in">traves</span>(root-&gt;left, k);</span><br><span class="line"></span><br><span class="line">        ++rank;</span><br><span class="line">        <span class="keyword">if</span>(rank == k)</span><br><span class="line">        &#123;</span><br><span class="line">            res = root-&gt;val;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;           </span><br><span class="line"></span><br><span class="line">        <span class="built_in">traves</span>(root-&gt;right, k);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">kthSmallest</span><span class="params">(TreeNode* root, <span class="keyword">int</span> k)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="built_in">traves</span>(root,k);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="236-二叉树的最近公共祖先"><a href="#236-二叉树的最近公共祖先" class="headerlink" title="236. 二叉树的最近公共祖先"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/">236. 二叉树的最近公共祖先</a></h4><p>    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。</p>
<p>    最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（<strong>一个节点也可以是它自己的祖先</strong>）。” </p>
<p><strong>示例 1：</strong></p>
<p><img src="/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/1.png" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [3,5,1,6,2,0,8,null,null,7,4], p &#x3D; 5, q &#x3D; 1</span><br><span class="line">输出：3</span><br><span class="line">解释：节点 5 和节点 1 的最近公共祖先是节点 3 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<p><img src="/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/2.png" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [3,5,1,6,2,0,8,null,null,7,4], p &#x3D; 5, q &#x3D; 4</span><br><span class="line">输出：5</span><br><span class="line">解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [1,2], p &#x3D; 1, q &#x3D; 2</span><br><span class="line">输出：1</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  树中节点数目在范围 <code>[2, 105]</code> 内。</li>
<li>  <code>-109 &lt;= Node.val &lt;= 109</code></li>
<li>  所有 <code>Node.val</code> <code>互不相同</code> 。</li>
<li>  <code>p != q</code></li>
<li>  <code>p</code> 和 <code>q</code> 均存在于给定的二叉树中。</li>
</ul>
<p><strong>思路与代码</strong>：</p>
<p>    递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root，表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:</p>
<ul>
<li>  左右子树的返回值都不为<code>nullptr</code>，由于值唯一左右子树的返回值就是<code>p</code>和<code>q</code>, 此时<code>root</code>为LCA</li>
<li>  左右子树返回值只有一个不为<code>nullptr</code>, 说明只有<code>p</code>和<code>q</code>存在与左或右子树中, 最先找到的那个节点为LCA</li>
<li>  左右子树返回值均为<code>nullptr</code>, <code>p</code>和<code>q</code>均不在树中, 返回<code>nullptr</code></li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">TreeNode* <span class="title">lowestCommonAncestor</span><span class="params">(TreeNode* root, TreeNode* p, TreeNode* q)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="keyword">if</span>(root == p || root == q)</span><br><span class="line">            <span class="keyword">return</span> root;</span><br><span class="line"></span><br><span class="line">        TreeNode* left = <span class="built_in">lowestCommonAncestor</span>(root-&gt;left, p, q);</span><br><span class="line">        TreeNode* right = <span class="built_in">lowestCommonAncestor</span>(root-&gt;right, p, q);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span>(left != <span class="literal">nullptr</span> &amp;&amp; right != <span class="literal">nullptr</span>)</span><br><span class="line">            <span class="keyword">return</span> root;</span><br><span class="line">        <span class="keyword">if</span>(left == <span class="literal">nullptr</span> &amp;&amp; right == <span class="literal">nullptr</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="keyword">return</span> left == <span class="literal">nullptr</span> ? right : left;          </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h4 id="538-把二叉搜索树转换为累加树"><a href="#538-把二叉搜索树转换为累加树" class="headerlink" title="538. 把二叉搜索树转换为累加树"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/convert-bst-to-greater-tree/">538. 把二叉搜索树转换为累加树</a></h4><p>&ensp;&ensp;&ensp;&ensp;给出二叉 <strong>搜索</strong> 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 <code>node</code> 的新值等于原树中大于或等于 <code>node.val</code> 的值之和。</p>
<p>&ensp;&ensp;&ensp;&ensp;提醒一下，二叉搜索树满足下列约束条件：</p>
<ul>
<li>  节点的左子树仅包含键 <strong>小于</strong> 节点键的节点。</li>
<li>  节点的右子树仅包含键 <strong>大于</strong> 节点键的节点。</li>
<li>  左右子树也必须是二叉搜索树。</li>
</ul>
<p><strong>示例 1：</strong></p>
<p><strong><img src="/myblog/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/3.png" alt="img" style="zoom:33%;"></strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]</span><br><span class="line">输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [0,null,1]</span><br><span class="line">输出：[1,null,1]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [1,0,2]</span><br><span class="line">输出：[3,3,2]</span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [3,2,4,1]</span><br><span class="line">输出：[7,9,4,10]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  树中的节点数介于 <code>0</code> 和 <code>104</code> 之间。</li>
<li>  每个节点的值介于 <code>-104</code> 和 <code>104</code> 之间。</li>
<li>  树中的所有值 <strong>互不相同</strong> 。</li>
<li>  给定的树为二叉搜索树</li>
</ul>
<p><strong>思路与代码</strong>：</p>
<p>&ensp;&ensp;&ensp;&ensp;这不就是中序遍历中，每一个节点的值加上后面所有结点的值的遍历结果吗？为了方便累加，我们改变中序遍历的顺序，先遍历右子树，再遍历左子树。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">    <span class="function">TreeNode* <span class="title">convertBST</span><span class="params">(TreeNode* root)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="built_in">travers</span>(root);</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">travers</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        <span class="built_in">travers</span>(root-&gt;right);</span><br><span class="line"></span><br><span class="line">        sum += root-&gt;val;</span><br><span class="line">        root-&gt;val = sum;</span><br><span class="line"></span><br><span class="line">        <span class="built_in">travers</span>(root-&gt;left);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h4 id="652-寻找重复的子树"><a href="#652-寻找重复的子树" class="headerlink" title="652. 寻找重复的子树"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-duplicate-subtrees/">652. 寻找重复的子树</a></h4><p>&ensp;&ensp;&ensp;&ensp;给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意<strong>一棵</strong>的根结点即可。</p>
<p>&ensp;&ensp;&ensp;&ensp;两棵树重复是指它们具有相同的结构以及相同的结点值。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">    1</span><br><span class="line">   &#x2F; \</span><br><span class="line">  2   3</span><br><span class="line"> &#x2F;   &#x2F; \</span><br><span class="line">4   2   4</span><br><span class="line">   &#x2F;</span><br><span class="line">  4</span><br></pre></td></tr></table></figure>

<p>下面是两个重复的子树：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">  2</span><br><span class="line"> &#x2F;</span><br><span class="line">4</span><br></pre></td></tr></table></figure>

<p>和</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">4</span><br></pre></td></tr></table></figure>

<p>&ensp;&ensp;&ensp;&ensp;因此，你需要以列表的形式返回上述重复子树的根结点。</p>
<p><strong>思路与代码</strong>：</p>
<p>&ensp;&ensp;&ensp;&ensp;采用将二叉树序列化的形式，建立哈希表，统计每次出现的次数，添加到结果集当中。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">vector&lt;TreeNode*&gt; <span class="title">findDuplicateSubtrees</span><span class="params">(TreeNode* root)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">          vector&lt;TreeNode*&gt; result;</span><br><span class="line">          unordered_map&lt;string,<span class="keyword">int</span>&gt; mp;</span><br><span class="line">          <span class="built_in">helper</span>(root, result, mp);</span><br><span class="line"></span><br><span class="line">          <span class="keyword">return</span> result;  </span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function">string <span class="title">helper</span><span class="params">(TreeNode* root, </span></span></span><br><span class="line"><span class="function"><span class="params">                vector&lt;TreeNode*&gt; &amp;result, </span></span></span><br><span class="line"><span class="function"><span class="params">                unordered_map&lt;string,<span class="keyword">int</span>&gt; &amp;mp)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span> <span class="string">&quot;#&quot;</span>;</span><br><span class="line"></span><br><span class="line">        string str = <span class="built_in">helper</span>(root-&gt;left, result, mp) + <span class="string">&quot;,&quot;</span> + </span><br><span class="line">                     <span class="built_in">helper</span>(root-&gt;right, result, mp) + <span class="string">&quot;,&quot;</span> + </span><br><span class="line">                     <span class="built_in">to_string</span>(root-&gt;val);</span><br><span class="line">                     </span><br><span class="line">        <span class="keyword">if</span>(mp[str] == <span class="number">1</span>)</span><br><span class="line">            result.<span class="built_in">push_back</span>(root);</span><br><span class="line">        mp[str]++;</span><br><span class="line">        <span class="keyword">return</span> str;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="700-二叉搜索树中的搜索"><a href="#700-二叉搜索树中的搜索" class="headerlink" title="700. 二叉搜索树中的搜索"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/search-in-a-binary-search-tree/">700. 二叉搜索树中的搜索</a></h4><p>&ensp;&ensp;&ensp;&ensp;给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。</p>
<p>&ensp;&ensp;&ensp;&ensp;例如，</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">给定二叉搜索树:</span><br><span class="line"></span><br><span class="line">        4</span><br><span class="line">       &#x2F; \</span><br><span class="line">      2   7</span><br><span class="line">     &#x2F; \</span><br><span class="line">    1   3</span><br><span class="line"></span><br><span class="line">和值: 2</span><br></pre></td></tr></table></figure>

<p>&ensp;&ensp;&ensp;&ensp;你应该返回如下子树:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">  2     </span><br><span class="line"> &#x2F; \   </span><br><span class="line">1   3</span><br></pre></td></tr></table></figure>

<p>&ensp;&ensp;&ensp;&ensp;在上述示例中，如果要找的值是 <code>5</code>，但因为没有节点值为 <code>5</code>，我们应该返回 <code>NULL</code>。</p>
<p><strong>思路与代码</strong>：</p>
<p>&ensp;&ensp;&ensp;&ensp;没什么好说的，直接遍历即可。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">TreeNode* <span class="title">searchBST</span><span class="params">(TreeNode* root, <span class="keyword">int</span> val)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="keyword">if</span>(val &gt; root-&gt;val)</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">searchBST</span>(root-&gt;right, val);</span><br><span class="line">        <span class="keyword">if</span>(val &lt; root-&gt;val)</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">searchBST</span>(root-&gt;left, val);</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="701-二叉搜索树中的插入操作"><a href="#701-二叉搜索树中的插入操作" class="headerlink" title="701. 二叉搜索树中的插入操作"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/">701. 二叉搜索树中的插入操作</a></h4><p>&ensp;&ensp;&ensp;&ensp;给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 <strong>保证</strong> ，新值和原始二叉搜索树中的任意节点值都不同。</p>
<p>&ensp;&ensp;&ensp;&ensp;<strong>注意</strong>，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 <strong>任意有效的结果</strong> 。</p>
<p><strong>示例 1：</strong></p>
<img src="/myblog/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98/4.jpg" alt="img" style="zoom:50%;">

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [4,2,7,1,3], val &#x3D; 5</span><br><span class="line">输出：[4,2,7,1,3,5]</span><br><span class="line">解释：另一个满足题目要求可以通过的树是：</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [40,20,60,10,30,50,70], val &#x3D; 25</span><br><span class="line">输出：[40,20,60,10,30,50,70,null,null,25]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：root &#x3D; [4,2,7,1,3,null,null,null,null,null,null], val &#x3D; 5</span><br><span class="line">输出：[4,2,7,1,3,5]</span><br></pre></td></tr></table></figure>

<p> <strong>提示：</strong></p>
<ul>
<li>  给定的树上的节点数介于 <code>0</code> 和 <code>10^4</code> 之间</li>
<li>  每个节点都有一个唯一整数值，取值范围从 <code>0</code> 到 <code>10^8</code></li>
<li>  <code>-10^8 &lt;= val &lt;= 10^8</code></li>
<li>  新值和原始二叉搜索树中的任意节点值都不同</li>
</ul>
<p><strong>思路与代码</strong>：</p>
<p>&ensp;&ensp;&ensp;&ensp;遍历找到合适的位置，再插入。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">TreeNode* <span class="title">insertIntoBST</span><span class="params">(TreeNode* root, <span class="keyword">int</span> val)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="built_in">TreeNode</span>(val);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span>(val &gt; root-&gt;val)</span><br><span class="line">            root-&gt;right = <span class="built_in">insertIntoBST</span>(root-&gt;right, val);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            root-&gt;left = <span class="built_in">insertIntoBST</span>(root-&gt;left, val);</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="450-删除二叉搜索树中的节点"><a href="#450-删除二叉搜索树中的节点" class="headerlink" title="450. 删除二叉搜索树中的节点"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/delete-node-in-a-bst/">450. 删除二叉搜索树中的节点</a></h4><p>&ensp;&ensp;&ensp;&ensp;给定一个二叉搜索树的根节点 <strong>root</strong> 和一个值 <strong>key</strong>，删除二叉搜索树中的 <strong>key</strong> 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。</p>
<p>&ensp;&ensp;&ensp;&ensp;一般来说，删除节点可分为两个步骤：</p>
<ol>
<li> 首先找到需要删除的节点；</li>
<li> 如果找到了，删除它。</li>
</ol>
<p><strong>说明：</strong> 要求算法时间复杂度为 O(h)，h 为树的高度。</p>
<p><strong>示例:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">root &#x3D; [5,3,6,2,4,null,7]</span><br><span class="line">key &#x3D; 3</span><br><span class="line"></span><br><span class="line">    5</span><br><span class="line">   &#x2F; \</span><br><span class="line">  3   6</span><br><span class="line"> &#x2F; \   \</span><br><span class="line">2   4   7</span><br><span class="line"></span><br><span class="line">给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。</span><br><span class="line"></span><br><span class="line">一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。</span><br><span class="line"></span><br><span class="line">    5</span><br><span class="line">   &#x2F; \</span><br><span class="line">  4   6</span><br><span class="line"> &#x2F;     \</span><br><span class="line">2       7</span><br><span class="line"></span><br><span class="line">另一个正确答案是 [5,2,6,null,4,null,7]。</span><br><span class="line"></span><br><span class="line">    5</span><br><span class="line">   &#x2F; \</span><br><span class="line">  2   6</span><br><span class="line">   \   \</span><br><span class="line">    4   7</span><br></pre></td></tr></table></figure>

<p><strong>思路与代码</strong>：</p>
<p>&ensp;&ensp;&ensp;&ensp;要删除的节点<code>A</code>有三种情况：</p>
<p>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;<code>A</code>恰好是末端节点，两个子节点都为空，那么它可以当场去世了。</p>
<p>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;<code>A</code>只有一个非空子节点，那么它要让这个孩子接替自己的位置。</p>
<p>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;<code>A</code>有两个子节点，麻烦了，为了不破坏 BST 的性质，<code>A</code>必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我采用第二种方式。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">TreeNode* <span class="title">getMin</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">while</span>(root-&gt;left)</span><br><span class="line">            root = root-&gt;left;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function">TreeNode* <span class="title">deleteNode</span><span class="params">(TreeNode* root, <span class="keyword">int</span> key)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="keyword">if</span>(key &gt; root-&gt;val)</span><br><span class="line">            root-&gt;right = <span class="built_in">deleteNode</span>(root-&gt;right, key);</span><br><span class="line">        <span class="keyword">if</span>(key &lt; root-&gt;val)</span><br><span class="line">            root-&gt;left = <span class="built_in">deleteNode</span>(root-&gt;left, key);</span><br><span class="line">        <span class="keyword">if</span>(key == root-&gt;val)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(!root-&gt;left) <span class="keyword">return</span> root-&gt;right;</span><br><span class="line">            <span class="keyword">if</span>(!root-&gt;right) <span class="keyword">return</span> root-&gt;left;</span><br><span class="line"></span><br><span class="line">            TreeNode* minNode = <span class="built_in">getMin</span>(root-&gt;right);</span><br><span class="line">            root-&gt;val = minNode-&gt;val;</span><br><span class="line">            root-&gt;right = <span class="built_in">deleteNode</span>(root-&gt;right, minNode-&gt;val);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p><a target="_blank" rel="noopener" href="https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247488128&idx=2&sn=b8fb3fd2917f9ac86127054741cd5877&chksm=9bd7ec88aca0659ee0185b657663169169493e9df2063fa4d28b38a0b4d0dd698d0301937898&scene=21#wechat_redirect">原创 | 手把手刷二叉搜索树（第二期） (qq.com)</a></p>

    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/myblog/tags/leetcode/" rel="tag"># leetcode</a>
              <a href="/myblog/tags/%E7%AE%97%E6%B3%95/" rel="tag"># 算法</a>
              <a href="/myblog/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/" rel="tag"># 二叉树</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/myblog/2021/05/06/Shell%EF%BC%9ALeetcode%E7%9A%84Shell%E4%B9%A0%E9%A2%98/" rel="prev" title="leetcode中的Shell习题">
      <i class="fa fa-chevron-left"></i> leetcode中的Shell习题
    </a></div>
      <div class="post-nav-item">
    <a href="/myblog/2021/05/07/%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%A0%91%E9%81%8D%E5%8E%86%E6%A8%A1%E6%9D%BF/" rel="next" title="二叉树的遍历模板">
      二叉树的遍历模板 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-4"><a class="nav-link" href="#98-%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="nav-text">98. 验证二叉搜索树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#102-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-text">102. 二叉树的层序遍历</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#230-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%AC%ACK%E5%B0%8F%E7%9A%84%E5%85%83%E7%B4%A0"><span class="nav-text">230. 二叉搜索树中第K小的元素</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#236-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88"><span class="nav-text">236. 二叉树的最近公共祖先</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#538-%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91"><span class="nav-text">538. 把二叉搜索树转换为累加树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#652-%E5%AF%BB%E6%89%BE%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E6%A0%91"><span class="nav-text">652. 寻找重复的子树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#700-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2"><span class="nav-text">700. 二叉搜索树中的搜索</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#701-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C"><span class="nav-text">701. 二叉搜索树中的插入操作</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#450-%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9"><span class="nav-text">450. 删除二叉搜索树中的节点</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="高乾威"
      src="/myblog/images/avatar.png">
  <p class="site-author-name" itemprop="name">高乾威</p>
  <div class="site-description" itemprop="description">报我楼成秋望月，把君诗读夜回灯</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/myblog/archives/">
        
          <span class="site-state-item-count">91</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/myblog/categories/">
          
        <span class="site-state-item-count">27</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/myblog/tags/">
          
        <span class="site-state-item-count">59</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="http://github.com/GaoQianwei" title="GitHub → http:&#x2F;&#x2F;github.com&#x2F;GaoQianwei" rel="noopener" target="_blank">GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:2966807184@qq.com" title="E-Mail → mailto:2966807184@qq.com" rel="noopener" target="_blank">E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.zhihu.com/people/xue-wu-zhi-jing-75-22" title="知乎 → https:&#x2F;&#x2F;www.zhihu.com&#x2F;people&#x2F;xue-wu-zhi-jing-75-22" rel="noopener" target="_blank">知乎</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://blog.csdn.net/weixin_45341339" title="CSDN → https:&#x2F;&#x2F;blog.csdn.net&#x2F;weixin_45341339" rel="noopener" target="_blank">CSDN</a>
      </span>
  </div>



      </div><div>
  <canvas id="canvasDiyBlock" style="width:60%;">当前浏览器不支持canvas，请更换浏览器后再试</canvas>
<script src="/myblog/js/custom/clock.js"></script>

</div>


    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2021-04 到 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">高乾威</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

<span class="post-meta-divider">|</span>

<div class="theme-info">
  <div class="powered-by"></div>
  <span class="post-count">全站共 117.2k 字</span>
</div>

<span class="post-meta-divider">|</span>
        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/myblog/lib/anime.min.js"></script>
  <script src="/myblog/lib/velocity/velocity.min.js"></script>
  <script src="/myblog/lib/velocity/velocity.ui.min.js"></script>

<script src="/myblog/js/utils.js"></script>

<script src="/myblog/js/motion.js"></script>


<script src="/myblog/js/schemes/pisces.js"></script>


<script src="/myblog/js/next-boot.js"></script>


  <script defer src="/myblog/lib/three/three.min.js"></script>
    <script defer src="/myblog/lib/three/canvas_lines.min.js"></script>


  




  
<script src="/myblog/js/local-search.js"></script>













  

  

</body>
</html>
